/**
 此方法比官方动态规划方法似乎快一点点
 * @param {number[]} height
 * @return {number}
 */
export var trap = function (height) {
  let ans = 0
  const peaks = findPeak(height)
  // console.log(peaks)
  if (peaks.length < 2) return 0
  for (let i = 0; i < peaks.length - 1; i++) {
    const left = peaks[i]
    const right = peaks[i + 1]
    ans += computeWater(height, left, right)
  }
  return ans
}

// 找出所有高点
function findPeak(height) {
  const peaks = []
  let i = 0
  let preMaxIdx = -1 // 记录上一个找到的最高点
  while (i < height.length) {
    const curH = height[i]
    let nextI = i + 1
    while (height[nextI] == curH) nextI++
    if (i === 0 && nextI === height.length) return []
    if (i === 0 && curH > height[nextI]) {
      peaks.push(i)
      preMaxIdx = i
      i = nextI + 1
    } else if (
      (i < height.length - 1 &&
        nextI < height.length &&
        curH > height[nextI] &&
        curH > height[i - 1]) ||
      (i === height.length - 1 && curH > height[i - 1]) ||
      (nextI >= height.length && curH > height[i - 1])
    ) {
      while (
        peaks.length &&
        height[peaks[peaks.length - 1]] < height[i] &&
        height[peaks[peaks.length - 1]] !== height[preMaxIdx]
      ) {
        peaks.pop()
      }
      peaks.push(i)
      if (curH > height[preMaxIdx] || preMaxIdx === -1) preMaxIdx = i
      // console.log('preMaxIdx', preMaxIdx)
      i += 2
    } else i++
  }
  return peaks
}

// 计算两个高点之间能装多少水
function computeWater(height, left, right) {
  let res = 0
  const h = Math.min(height[left], height[right])
  for (let i = left + 1; i < right; i++) {
    res += h - height[i] < 0 ? 0 : h - height[i]
  }
  return res
}

/**
 * 官方单调栈方法
 * @param {*} height
 * @returns
 */
export var trap2 = function (height) {
  let ans = 0
  const stack = []
  const n = height.length
  for (let i = 0; i < n; ++i) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop()
      if (!stack.length) {
        break
      }
      const left = stack[stack.length - 1]
      const currWidth = i - left - 1
      const currHeight = Math.min(height[left], height[i]) - height[top]
      ans += currWidth * currHeight
    }
    stack.push(i)
  }
  return ans
}
